package com.lw.leetcode.back.b;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 797. 所有可能的路径
 * 剑指 Offer II 110. 所有路径
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/25 12:53
 */
public class AllPathsSourceTarget {


    private List<List<Integer>> list = new ArrayList<>();
    private int[][] graph;
    private int[] arr;
    private int length;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        this.length = graph.length;
        this.graph = graph;
        this.arr = new int[length];
        find(0, 0);
        return list;
    }

    private void find(int index, int n) {
        if (n == length - 1) {
            List<Integer> values = new ArrayList<>(index + 1);
            for (int i = 0; i < index; i++) {
                values.add(arr[i]);
            }
            values.add(n);
            list.add(values);
            return;
        }
        int[] ints = graph[n];
        arr[index] = n;
        for (int anInt : ints) {
            find(index + 1, anInt);
        }
    }

}
